The present invention relates generally to sequential decoders for decoding convolutional code symbols, and more specifically to recovery of bit and symbol timing for a sequential decoder.
The technique of sequentially coding digital pulses, such as convolutional code symbols, is well known in the art because of its powerful error correcting capability. The convolutional codes are generated by a convolutional encoder which consists of a K-stage shift register, v-modulo 2 adders connected to some of the shift register stages, and a commutator that scans the output of the modulo 2 adders. The convolutional encoder processes the information bits continuously in a serial fashion, a few bits at a time, and appends some parity, or redundant bits to form code symbols. Sequential decoders include a replica of the encoder which decodes the convolutional code symbols according to a decoding algorithm. The Fano algorithm is the well known technique for convolutional codes. According to this algorithm, the received code symbols are decoded by the encoder replica to recover a replica of the original symbols. If the code symbols are two-bit symbols, the encoder replica produces an output which would be one of the four possible combinations of the two incoming bits and this output is compared with the incoming code symbols. The result of the comparison is used to hypothesize one of the possible combinations as the nearest to the incoming symbols according to what is known as the Fano likelihood decision. If a false decision is made in a decoding process, the discrepancy between the internal state of the encoder replica and the internal state of the encoder itself increases as the decoding process proceeds due to the increasing difficulty to find one having the maximum Fano likelihood value. The degree of this difficulty is used as a measure for detecting whether the decoder has made an error in the past decision. Under such circumstances, the decoding procedure is repeated on the hypothesis that the next higher Fano likelihood value that has been obtained in a past decision is the most likely symbol. The process is repeated by successively tracing backwards the tree structure of the codes to correct the error. A buffer is therefore provided to store as many incoming symbols as is necessary to repeat the hypothesis on a trial-and-error basis. However, a buffer overflow and possible communication breakdown are likely to occur under noisy environment. Recovering procedures are usually applied during buffer overflows, which occur with a relatively large probability.
Bit timing and symbol timing errors are the potential sources of errors that could lead to a false decision in the sequential decoding process. Prior art recovering procedures, for example as shown and described in U.S. Pat. No. 4,878,221, involve skipping a portion of stored code symbols in response to the occurrence of a buffer overflow and shifting the bit timing of incoming code symbols by a unit value and then resetting the sequential decoder to clear its internal state. The process is repeated as long as the buffer overflow exists. However, one disadvantage of the prior art recovery procedures is that even though the correct bit timing is reestablished, it is unnecessarily shifted as long as the overflow continues. As a result, once a buffer overflow occurs, it tends to trigger a subsequent overflow and as a result a substantial amount of data must be discarded.